/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName   : Leetcode0438 
 * @author      : ganwei 
 * @date        : 2020年5月19日
 * @Description : Leetcode0438 找到字符串中所有字母异位词
 */
public class Leetcode0438 {
    List<Integer> result = new ArrayList<>();
	/**
     * -解题思路，滑窗算法
     */
	public List<Integer> findAnagrams(String s, String p) {
		int left = 0, right = 0;
		
		Map<Character, Integer> window = new HashMap<Character, Integer>();
		Map<Character, Integer> needs = new HashMap<Character, Integer>();
		
		for(int i = 0; i < p.length(); i++) {
			int count = needs.getOrDefault(p.charAt(i), 0);
			needs.put(p.charAt(i), count + 1);
		}
		
		int match = 0;
		
		while(right < s.length()) {
			char c = s.charAt(right);
			int count = window.getOrDefault(c, 0);
			window.put(c, count + 1);
			
			if(needs.containsKey(c) && window.get(c).intValue() == needs.get(c).intValue()) {
				match++;
			}
			while(left <= right && match == needs.size()) {
				char c1 = s.charAt(left);
				if(right-left+1 == p.length()) {
					result.add(left);
				}
				
				window.put(c1, window.get(c1)-1);
				if(needs.containsKey(c1) && window.get(c1).intValue() == 0) {
					match--;
				}
				left++;
			}
			
			
			right++;
		}
		
    	return result;
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	String s = "cbaebabacd";
    	String p = "abc";
    	Leetcode0438 l0438 = new Leetcode0438();
    	System.out.println(l0438.findAnagrams(s, p));
    }
}
